package LeetCode;

public class RegexMatch
{
  //just remember
  public boolean isMatch(String s, String p)
  {
    char[] str1 = s.toCharArray();
    char[] str2 = p.toCharArray();
    return isMatch(str1, str2, 0, 0);
  }

  public boolean isMatch(char[] str1, char[] str2, int start1, int start2)
  {
    if (start2 == str2.length) return start1 == str1.length;

    // if next is not *
    if (!(start2 < str2.length - 1 && str2[start2 + 1] == '*')) {
      return (start1 < str1.length)
          && (str1[start1] == str2[start2] || str2[start2] == '.')
          && isMatch(str1, str2, start1 + 1, start2 + 1);
    }
    
    //if next is *
    while(start1 < str1.length && start2 < str2.length && (str1[start1] == str2[start2] || str2[start2] == '.')){
      if(isMatch(str1,str2,start1,start2+2))
        return true;
      start1++;
    }
    return isMatch(str1,str2,start1,start2+2);

  }

  /**
   * @param args
   */
  public static void main(String[] args)
  {
    // TODO Auto-generated method stub

  }

}
